package com.leetcode.offer.chapter5;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author Dennis Li
 * @date 2020/7/18 11:05
 */
public class MaxQueue_59 {

    Queue<Integer> queue;
    Deque<Integer> aux;

    public MaxQueue_59() {
        queue = new LinkedList<>();
        aux = new LinkedList<>();
    }

    public int max_value() {
        return aux.isEmpty() ? -1 : aux.peekFirst();
    }

    public void push_back(int value) {
        queue.offer(value);
        // 单调队列和单调栈
        while(!aux.isEmpty() && aux.peekLast() < value)
            aux.pollLast();
        aux.offer(value);
    }

    public int pop_front() {
        if (!aux.isEmpty() && queue.peek().equals(aux.peekFirst()))
            aux.pollFirst();
        return queue.isEmpty() ? -1 : queue.poll();
    }

}
